package com.lfs.linkedlist;

/*
    判断是否为环 阶段1即可

    如果链表上存在环，那么在环上以不同速度前进的两个指针必定会在某个时刻相遇。算法分为两个阶段

    阶段1
    * 龟一次走一步，兔子一次走两步
    * 当兔子能走到终点时，不存在环
    * 当兔子能追上龟时，可以判断存在环

    阶段2
    * 从它们第一次相遇开始，龟回到起点，兔子保持原位不变
    * 龟和兔子一次都走一步
    * 当再次相遇时，地点就是环的入口

    为什么呢？
    * 设起点到入口走 a 步（本例是 7），绕环一圈长度为 b（本例是 5），
    * 那么**从起点开始，走 a + 绕环 n 圈，都能找到环入口**
    * 第一次相遇时
      * 兔走了 a + 绕环 n 圈（本例 2 圈） + k，k 是它们相遇距环入口位置（本例 3，不重要）
      * 龟走了 a + 绕环 n 圈（本例 0 圈） + k，当然它绕的圈数比兔少
      * 兔走的距离是龟的两倍，所以**龟走的** = 兔走的 - 龟走的 = **绕环 n 圈**
            此时相遇之后，假设兔子为龟，那么再走a就能到起点位置(龟走的距离 = 绕环n圈)
    * 而前面分析过，如果走 a + 绕环 n 圈，都能找到环入口，因此从相遇点开始，再走 a 步，就是环入口
 */
public class HasCycle141 {

    public boolean hasCycle(ListNode head) {
        ListNode h = head; // 兔子
        ListNode t = head; // 乌龟

        while (h != null && h.next != null) { // 因为兔子走两步，为避免空指针多加个判断
            t = t.next;
            h = h.next.next;
            if (t == h) {// 相遇则为环
                return true;
            }
        }
        // 不为环
        return false;
    }
}
